package com.aqie.medium.backtrack;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 78 子集, 不含重复元素的整数数组  TODO 要素很多
 * A中有n个元素，则A有2^n个子集，（2^n-1）个真子集，（2^n-2）个非空真子集
 */
public class Subsets {
    /**
     * 1，回溯算法： 不合适就回退上一步， 通过约束条件减少时间复杂度 3ms
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length == 0) return res;
        backtrack(0, nums, res, new ArrayList<Integer>());
        return res;
    }

    private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
        res.add(new ArrayList<>(tmp));
        for (int j = i; j < nums.length; j++) {
            tmp.add(nums[j]);
            backtrack(j + 1, nums, res, tmp);
            tmp.remove(tmp.size() - 1);
        }
    }

    /**
     * 2, 迭代,循环枚举 2ms
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets2(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        res.add(new ArrayList<>());
        for (Integer n : nums) {
            int size = res.size();
            for (int i = 0; i < size; i++) {
                List<Integer> newSub = new ArrayList<>(res.get(i));
                newSub.add(n);
                res.add(newSub);
            }
        }
        return res;
    }

    /**
     * 3. 位运算 2ms
     */
    public List<List<Integer>> subsets3(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < (1 << nums.length); i++) {
            List<Integer> sub = new ArrayList<Integer>();
            for (int j = 0; j < nums.length; j++)
                if (((i >> j) & 1) == 1) sub.add(nums[j]);
            res.add(sub);
        }
        return res;
    }


    /*
     递归不用全局变量
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
         res.add(new ArrayList<>());
        recursion( nums, 0,res);
        return res;
    }

    private void recursion(int[] nums, int i,  List<List<Integer>> res) {
        if (i >= nums.length) return;
        int size = res.size();
        for (int j = 0; j < size; j++) {
            List<Integer> newSub = new ArrayList<>(res.get(j));
            newSub.add(nums[i]);
            res.add(newSub);
        }
        recursion(nums, i + 1,res);
    }
     */
    /**
     * todo
     * 逐个枚举，空集的幂集只有空集，每增加一个元素，
     * 让之前幂集中的每个集合，追加这个元素，就是新增的子集
     * 4,递归枚举 1ms
     */
    List<List<Integer>> res = new ArrayList<>();
    public  List<List<Integer>> subsets4(int[] nums) {
        res.add(new ArrayList<>());
        recursion( nums, 0);
        return res;
    }

    private  void recursion(int[] nums, int i) {
        if (i >= nums.length) return;
        int size = res.size();
        for (int j = 0; j < size; j++) {
            List<Integer> newSub = new ArrayList<>(res.get(j));
            newSub.add(nums[i]);
            res.add(newSub);
        }
        recursion(nums, i + 1);
    }


    /**
     * 1ms
     * 5, 集合中每个元素 选与不选，构成一个满二叉树，左子树不选，右子树是选
     * 根节点到叶子节点的所有路径, 构成所有子集 (前序 中序 后序三种写法)
     * @param nums
     * @return
     */
    public static List<List<Integer>> subsets5(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length == 0) return res;
        preOrder( nums, 0, new ArrayList<>(), res);
        res.add(new ArrayList<>());
        return res;
    }

    private static void preOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) {
        if (i >= nums.length) return;
        // 到了新的状态，记录新的路径，要重新拷贝一份
        subset = new ArrayList<>(subset);

        // 这里
        res.add(subset);
        preOrder(nums, i + 1, subset, res);
        subset.add(nums[i]);
        preOrder(nums, i + 1, subset, res);
    }

    /**
     * 6,DFS，中序遍历 2ms
     */
    private static void inOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) {
        if (i >= nums.length) return;
        subset = new ArrayList<Integer>(subset);

        inOrder(nums, i + 1, subset, res);
        subset.add(nums[i]);
        // 这里
        res.add(subset);
        inOrder(nums, i + 1, subset, res);
    }


    /**
     * 7,DFS，后序遍历 2ms
     */
    private static void postOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) {
        if (i >= nums.length) return;
        subset = new ArrayList<Integer>(subset);

        postOrder(nums, i + 1, subset, res);
        subset.add(nums[i]);
        postOrder(nums, i + 1, subset, res);
        // 这里
        res.add(subset);
    }


    /**
     * 9,左子树选 右子树不选，元素入栈遍历左子树； (最近入栈)元素出栈， 遍历右子树 1ms
     */
    public List<List<Integer>> subsets6(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length == 0) return res;
        newPreOrder( nums, 0, new LinkedList<>(), res);
        res.add(new ArrayList<>());
        return res;
    }
    private static void newPreOrder(int[] nums, int i, LinkedList<Integer> stack, List<List<Integer>> res) {
        if (i >= nums.length) return;
        stack.push(nums[i]);
        // 这里
        res.add(new ArrayList<Integer>(stack));
        newPreOrder(nums, i + 1, stack, res);
        stack.pop();
        newPreOrder(nums, i + 1, stack, res);
    }


    public static void main(String[] args) {
        int[] nums = {1,2};
        System.out.println(subsets5(nums));

    }

}